Line & circle drawing algorithms.

elmm/[KCN]

If you are going to write a demo or any other program that'll draw some graphic primitives you will need to draw lines as a base of many primitives. No matter whether you use DX or OGL or you are writing directly to the video memory as in old times :) you will need your own line drawing algorithm. This article will help you to solve this problem...

In this article I'll explain two line drawing algorithms and one algorithm for circles. In real life DDA isn't used because it don't fast enough and gives bad result. But it is the simplest algorithm and I advise you to read it too if you are a beginner.

Let's go :)

DDA (Digital Difference Algorithm) - is the simplest algorithm, based on the function of the line - y=k*x+b. We already have two points that belong to the line - it's the begin and the end of the line (y1,x1-y2,x2), so we can find the k and b coefficients:

       y1 = k*x1+b
       y2 = k*x2+b

       k = (y2-y1)/(x2-x1)
       b = y1 - k*x1

I think this was very simple. Now we can move from x1 to x2, calculate and round y (if you use integer numbers the algorithm will not work) and draw pixels. But there is one little trouble - if the y part of the line is greater than the x part, then the line will have holes between the pixels. In this case you have to move from y1 to y2 and calculate x.

Here is the algorithm in C language…

void line_dda(int x1,int y1,int x2,int y2,int c) {
  float k,b,y;
  k = float((y2-y1))/(x2-x1);
  b = y1 - k*x1;
  if(x2<x1) {
    int t=x1; x1=x2; x2=t;
  };
  for(int x=x1;x>x2;x++) {
    y = k*x + b;
    putpixel(x,int(y),c);
  };
}

Now when you know the basics we can move to Bresenham's algorithm.

Let us have the function of our line represented as Dy (x-x1) - Dx (y-y1) = 0 ,(0), where Dx = x2 - x1, Dy = y2 - y1. (All this can be derived from y=k*x+b.) Let us take any point (xi,yi) which is very close to our line but doesn't belong to it. Then if we put this point to (0) we get:

    Dy (xi-x1) - Dx (yi-y1) = e (xi,yi) = e[i],                        (1)

Where e[i] (e[i] is not an array, I denoted it in this way to show that I is the index, and we'll have several e[…]) determines the deviation (xi,yi) from our line, at that

e(x1,y1) = e(x2,y2) = 0

As 0<= (Dy/Dx) <=1, then the next (i+1) point must be chosen from two points: (xi + 1, yi) or (xi + 1,yi + 1). If we put these coordinates to (1), we get:

   e [i+1]   (+1,0)  = Dy (xi + 1 - x1) - Dx (yi - y1)     =  e[i] + Dy ,
   e [i+1]   (+1,+1) = Dy (xi + 1 - x1) - Dx (yi + 1 -y1 ) =  e[i] + Dy - Dx .

It's easy to understand that we have to choose the point with smallest |e(i+1)|, in other words the point (x(i+1),y(i+1)) = (xi+1,yi+dy) , where:

  dy  =  | 0,  if | e[i+1]  (+1,0) |  <=  | e[i+1]  (+1,+1) |          (2)
  dy  =  | 1,  if | e[i+1]  (+1,0) |   >  | e[i+1]  (+1,+1) |

Because Dx>0, e[i+1](+1,0)>e[i+1](+1,+1) is always true, we can transform (2) to a test of the sign of the simple average of e(i+1) (+1,0), e(i+1) (+1,+1). Usually it's calculated as a doubled simple average.

S = e(i+1) (+1,0) + e(i+1) (+1,+1). Then

S = 2ei + 2Dy - Dx ,

  dy  =< | 0 |, if S <= 0                                           (3)
  dy  =< | 1 |, if S >  0

  2*e[i+1] = |  2*e[i] + 2*Dy  | ,        if S <= 0
  2*e[i+1] = |  2*e[i] + 2*Dy - 2*Dx  | , if  S > 0

Calculations of S, dy, 2e[i+1] using (3) don't need multiplication and division with floating point. That's why this algorithm is faster than the previous one.

C algorithm.

void line_brs(int x1,int y1,int x2,int y2,int c) {
  int Dx = (x2 - x1);
  int Dy = (y2 - y1);
  int DDy =  2*Dy; //(èëè DDy = Dy<<1;)
  int _2e = 0;
  int x = x1;
  int y = y1;
  putpixel(x,y,c);

  while((x /= x2)&&(y /= y1)) {
    x++;
    int S = _2e + DDy - Dx;

    if(S>0) {
      y++;
      _2e = S - Dx;
    }
    else {
      _2e = S + Dx;
    };
    putpixel(x,y,c);
}

And here is the circle drawing algorithm. The best property of circles is that they are symmetrical. Using this wonderful property we can draw pixels only for the first 45 degrees. And duplicate them. The algorithm of Bresenham is doing this thing. We suppose that the circle is in the center of the coordinate system:

   putpixel(Xc+x,Yc+y);
   putpixel(Xc+x,Yc-y);
   putpixel(Xc-x,Yc+y);
   putpixel(Xc-x,Yc-y);
   putpixel(Xc+y,Yc+x);
   putpixel(Xc+y,Yc-x);
   putpixel(Xc-y,Yc+x);
   putpixel(Xc-y,Yc-x);

We have to do such initialization routines using the radius of the circle:

  d = 3 - 2*radius;
  x = 0;
  y = radius;

Then for every calculated point we do:

  if(d<0) {
    d = d +(4*x) + 6;
  }
  else {
    d = d +4*(x - y) + 10;
    y = y + 1;
  }
  x = x + 1;

We repeat this until x is become equal to y.

Here is the C algorithm.

void circle32(int Xc,int Yc,int radius,int c) {
  int x,y,d;

  d = 3 - (radius<<1);
  x = 0;
  y = radius;

  while(x<y) {>p>
   putpixel(Xc+x,Yc+y,c);
   putpixel(Xc+x,Yc-y,c);
   putpixel(Xc-x,Yc+y,c);
   putpixel(Xc-x,Yc-y,c);
   putpixel(Xc+y,Yc+x,c);
   putpixel(Xc+y,Yc-x,c);
   putpixel(Xc-y,Yc+x,c);
   putpixel(Xc-y,Yc-x,c);

   if(d>0) {
     d = d + (x<<2) + 6;
   }
   else {
     d = d + ((x-y)<<2) + 10;
     y--;
   }
   x++;
  }
}

elmm/[KCN]